package com.zdb.algorithm.dynamicprogramming;

import java.util.Arrays;

public class KnapsackProblem {

    public static void main(String[] args) {
        // 下标对应商品的重量
        int[] w = {3, 4, 1};
        // 下标对应商品的价值
        int[] vals = {2000, 3000, 1500};
        // 背包的最大容量
        int m = 4;

        // v[i][j] 代表第i个商品在容量为j时能放的最大价值
        int[][] v = new int[w.length + 1][m + 1];

        // 将v[0][j],v[i][0] 设置为0,
        // v[0][j]代表0个商品放入时价值为0，v[i][0]背包容量为0时价值为0
        for(int j=0; j<v[0].length; j++) {
            v[0][j] = 0;
        }
        for(int i=0; i<v.length; i++) {
            v[i][0] = 0;
        }

        // 一行一行，从小到大计算v[i][j]
        for(int i=1; i<v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                // 判断 w[i-1] >= j时，v[i][j]= max{上一个格子的值， 当前商品放入后 + 上一个格子在j-w[i-1]容量的值 }
                if(w[i-1] <= j) {
                    v[i][j] = Math.max(v[i-1][j], vals[i-1] + v[i-1][j-w[i-1]]);
                } else {
                    // 如果当前商品的重量大于容量，则取上一个格子的值
                    v[i][j] = v[i-1][j];
                }

            }
        }


        // 打印
        for (int i = 0; i < v.length; i++) {
            System.out.println(Arrays.toString(v[i]));
        }

        // 打印组合
        // 先找到最后一列中最大的值第一次出现的位置
        int iIdx = w.length;
        int j = m;
        while(iIdx > 0 && j > 0) {

            if(v[iIdx][j] > v[iIdx - 1][j]) {
                System.out.println("第" + iIdx + "个商品放入背包");
                j = j-w[iIdx-1];
            } else {
                iIdx --;
            }

        }

    }
}
